ОСОБЕННОСТИ ПОСТРОЕНИЯ КОРРЕКТИРУЮЩЕГО АЛГОРИТМА

Матрица вероятностей переходов после корректировки НС В ПОЛ­НОЙ мере соответствует требованиям, предъявляемым к матрице Q кин шдачи линейного программирования. Основное отличие состо — ПІ и гом, что после корректировки она соответствует эргодической, а не поглощающей цепи Маркова, входящей в формулировку зада­чи линейного программирования. Механическая замена матрицы <ріодической цепи на матрицу с поглощением нс всегда позволяет получить решение задачи квадратичного программирования. Для и и о чтобы убедиться в этом, рассмотрим выражение типа (6.16) і ли / /■. Учитывая, что <7ю?(т+1) = 1,

F—1

2 л/(т)0,//г(т+[4]) + гї/'(1ґ)=:ГЕ/'(‘с+1)- (6.26)

1=1

< лецонательно, для случая, когда <7,•*•(?+1) >0, это равенство t П[мИе ІЛИПО При Лр(т+ 1) >Яіг(т) . Если же Яіг(т-Ь 1) =Пв(г), то

«?іР(т+1) =0 для всех i= 1, 2,F—1, и существуют два эргодиче — ских класса состояний, что противоречит исходной постановке за­дачи. При Як(т+ 1) <jtf(t) решение вообще не существует. Воз­можность использования алгоритма квадратичного программирова­ния для корректировки матрицы поглощающей цепи связана с пре­образованием исходной цепи с поглощением в псевдоэргодическую путем введения фиктивного перехода из поглощающего состояния в начальное с некоторой вероятностью а>0. В этом случае (6.26) принимает вид

F—1

2 Мт)9гиСг-И) + М*)(1 — а)=я/г(т+1),

i=i

существует один эргодический класс состояний и возможность ис­пользования методики § 6.3.

Введение псевдоэргодической цепи приводит также к тому, что распределение в момент т+1 зависит от а. Однако известно [46], что Ншя<“)(т-|- 1) = я(т+ 1). Отсюда следует, ЧТО при Предель­

но

ном переходе по а получающаяся псевдоэргодическая матрица Q(a) будет с точностью до финального распределения т(т +1) схо­диться к матрице с поглощением.

Отметим еще одну особенность решения, получаемого с помо­щью алгоритма квадратичного программирования: отдельные эле­менты qiF оказываются равными нулю (например, для матрицы 4×4 это элемент q^F, см. § 6.3). Такая матрица не отражает в пол­ной мере процесс изменения технического состояния АС. В самом деле, всегда существует ненулевая вероятность отказа при любом исходном состоянии іє 1, F—1. Чтобы учесть это, целесообразно в ограничения задачи (6.20) ввести условия qiF (т-f-l) >0, г є 1

элементы МВП корректируются с использованием формулиров — мі задачи в виде (6.19, 6.20, 6.27 и 6.28); осуществляется предельный переход по а.

Найденная матрица используется при решении задач линейного программирования (см. § 3.1—3.4).

Глава VII